Tutorial 12: Advanced Examples

Programming for Engineers (ENGG1001)

Tutorial Tasks

• Task 1: Extend the Walker Class to include diagonal movement
• Task 2: Determine the average distance of each walker from its origin after a set number of steps

Task 1: Extend the Walker Simulation to Include Diagonal Movement

In the lectures, we used one particular type of random walk: our walker was restricted to 2-D motion and could take steps UP, DOWN, LEFT and RIGHT. Let us imagine that other types of step are allowed. We could allow the random walker more freedom to take steps on the diagonal also. This new random walker could take steps UP, UP-RIGHT, RIGHT, DOWN-RIGHT, DOWN, DOWN-LEFT, LEFT, and UP-LEFT, for a total of 8 different step types. These possible steps are shown in Figure 1.

Figure 1: Allowable steps for an 8-step-choice walker.

Extend the program random_walk.py to include a random walker type that is allowed to move in 8 directions. Simulate such a walker for 10,000 steps on a domain with L = 101 and plot the walker’s path. Random_walk.py is shown below:

random_walk.py

import random
import matplotlib.pyplot as plt
import numpy as np

LENGTH = 101
start_pos = (int(LENGTH/2), int(LENGTH/2)) # (i, j)
n_steps = 10000

class Walker4(object):
    """A 2D random walker with 4 step choices."""
    _step_choices = ('up', 'down', 'left', 'right')
    _step_dirn = {'up': (0, +1), # 0 in i, +1 in j
                  'down': (0, -1), # 0 in i, -1 in j
                  'left': (-1, 0), # -1 in i, 0 in j
                  'right': (+1, 0), # +1 in i, 0 in j
                  }

    def __init__(self, start_pos: tuple[int, int]):
        """Initialize walker at start_pos.
        
        Parameters
        ----------
        start_pos : tuple
            (i, j) starting position of the walker
        
        """
        self._pos = start_pos
        self._old_pos = start_pos

    def __str__(self):
        """String representation of the walker position.
        
        Returns
        -------
        str
            String representation of the walker position
        """
        return f"{self._pos}"

    def take_step(self):
        """Updates the walker's position by taking a random step in one of the allowed directions.
        """
        self._old_pos = self._pos
        step = random.choice(self._step_choices)
        dirn = self._step_dirn[step]
        self._pos = (self._pos[0] + dirn[0], self._pos[1] + dirn[1])

    def step_back(self):
        """Reverts the walker's position to the previous position.
        """
        self._pos = self._old_pos
        
    def get_position(self):
        """Returns the current position of the walker.

        Returns
        -------
        tuple
            (i, j) current position of the walker
        """
        return self._pos

class Path(object):
    """Accumulator of steps of a random walker."""

    def __init__(self):
        """Initialize an empty path.
        """
        self._path_x = []
        self._path_y = []

    def add_step(self, walker: Walker4):
        """Add the current position of the walker to the path.

        Parameters
        ----------
        walker : Walker4
            The random walker whose position is to be added to the path
        """
        pos = walker.get_position()
        self._path_x.append(pos[0])
        self._path_y.append(pos[1])

    def get_path(self):
        """Returns the x and y coordinates of the path.

        Returns
        -------
        tuple
            (path_x, path_y) lists of x and y coordinates of the path
        """
        return self._path_x, self._path_y

class Domain(object):
    """Represent extents of the computational domain for the walker."""

    def __init__(self, length: int):
        """Initialize the domain with size L.

        Parameters
        ----------
        L : int
            Size of the domain (L x L)
        """
        self._length = length

    def is_valid_position(self, walker: Walker4) -> bool:
        """Check if the walker's position is within the domain.

        Parameters
        ----------
        walker : Walker4
            The random walker whose position is to be checked

        Returns
        -------
        bool
            True if the position is valid, False otherwise
        """
        pos = walker.get_position()
        if pos[0] < 0: # stepped off the left end
            return False
        if pos[0] > self._length - 1: # stepped off the right end
            return False
        if pos[1] < 0: # stepped off the bottom
            return False
        if pos[1] > self._length - 1: # stepped off the top
            return False
        # anything else is good
        return True
    
def plot_path(path):
    """Plot the path of the walker.

    Parameters
    ----------
    path : Path
        The path of the walker to be plotted
    """
    path_x, path_y = path.get_path()
    fig, ax = plt.subplots()

    ax.plot(path_x, path_y, "-", c="blue", alpha=0.5)
    ax.plot(path_x[0], path_y[0], marker="+", c="black", markersize=6, markeredgewidth=2)
    ax.plot(path_x[-1], path_y[-1], marker="o", c="red", markersize=6)

    ax.set_xlim(0, LENGTH-1)
    ax.set_ylim(0, LENGTH-1)
    ax.set_aspect('equal')
    plt.show()

    
print("Starting position= ", start_pos)
walker = Walker4(start_pos)
path = Path()
path.add_step(walker)
domain = Domain(LENGTH)

for i in range(n_steps):
    walker.take_step()

    while not domain.is_valid_position(walker):
        walker.step_back()
        walker.take_step()

    path.add_step(walker)

print("Finish position= ", walker)

plot_path(path)

Output

Starting position=  (50, 50)
Finish position=  (21, 69)

Output

To achieve this goal, we will rework the design of the program. The main suggestion will be to build a parent class for all Walkers and the build subclasses for our original walker and the new walker. Here is a suggested plan-of-attack:

1. Build the new walker called Walker8 that can take a step in the eight allowed directions shown in Figure 1.
2. Look for the abstraction in the classes Walker4 and Walker8. Build an abstract base class called Walker and rework Walker4 and Walker8 so that they derive from Walker.

Tip

HINT: All of the methods can actually appear in the base class. Think about what is in common between the two walker types, and whether you can “factor out” the similaries.

Callout-answerAnswer

random_walk.py

import random
import matplotlib.pyplot as plt
import numpy as np
L = 101
start_pos = (int(L/2), int(L/2)) # (i, j)
n_steps = 10000

class Walker(object):
    """A base class for 2D random walkers."""
    _step_choices = ()
    _step_dirn = {}

    def __init__(self, start_pos):
        """Initialize walker at start_pos.

        Parameters
        ----------
        start_pos : tuple
            (i, j) starting position of the walker
        """
        self._pos = start_pos
        self._old_pos = start_pos

    def __str__(self) -> str:
        """String representation of the walker position.
        
        Returns
        -------
        str
            String representation of the walker position
        """
        return f"{self._pos}"

    def take_step(self):
        """Updates the walker's position by taking a random step in one of the allowed directions.
        """
        self._old_pos = self._pos
        step = random.choice(self._step_choices)
        dirn = self._step_dirn[step]
        self._pos = (self._pos[0] + dirn[0], self._pos[1] + dirn[1])

    def step_back(self):
        """Reverts the walker's position to the previous position.
        """
        self._pos = self._old_pos
        
    def get_position(self) -> tuple[int, int]:
        """Returns the current position of the walker.

        Returns
        -------
        tuple
            (i, j) current position of the walker
        """
        return self._pos

class Walker4(Walker):
    """A 2D random walker with 4 step choices."""

    _step_choices = ('up', 'down', 'left', 'right')

    _step_dirn = {'up': (0, +1), # 0 in i, +1 in j
                  'down': (0, -1), # 0 in i, -1 in j
                  'left': (-1, 0), # -1 in i, 0 in j
                  'right': (+1, 0), # +1 in i, 0 in j
                  }

class Walker8(Walker):
    """A 2D random walker with 8 step choices."""

    _step_choices = ('up', 'down', 'left', 'right', 'up-left', 'up-right', 'down-left', 'down-right')

    _step_dirn = {'up': (0, +1), # 0 in i, +1 in j
                  'down': (0, -1), # 0 in i, -1 in j
                  'left': (-1, 0), # -1 in i, 0 in j
                  'right': (+1, 0), # +1 in i, 0 in j
                  'up-left': (-1, +1),
                  'up-right': (+1, +1),
                  'down-left': (-1, -1),
                  'down-right': (+1, -1),
                  }


class Path(object):
    """Accumulator of steps of a random walker."""

    def __init__(self):
        """Initialize an empty path."""
        self._path_x = []
        self._path_y = []
    
    def add_step(self, walker):
        """Add the current position of the walker to the path.

        Parameters
        ----------
        walker : Walker
            The random walker whose position is to be added to the path
        """
        pos = walker.get_position()
        self._path_x.append(pos[0])
        self._path_y.append(pos[1])
    
    def get_path(self):
        """Returns the x and y coordinates of the path.
        
        Returns
        -------
        tuple
            (path_x, path_y) lists of x and y coordinates of the path
        """
        return self._path_x, self._path_y

class Domain(object):
    """Represent extents of the computational domain for the walker."""

    def __init__(self, length):
        """Initialize the domain with size L.

        Parameters
        ----------
        length : int
            Size of the domain (length x length)
        """
        self._length = length
    
    def is_valid_position(self, walker):
        """Check if the walker's position is within the domain.

        Parameters
        ----------
        walker : Walker
            The random walker whose position is to be checked
        
        Returns
        -------
        bool
            True if the position is valid, False otherwise
        """
        pos = walker.get_position()
        if pos[0] < 0: # stepped off the left end
            return False
        if pos[0] > self._length-1: # stepped off the right end
            return False
        if pos[1] < 0: # stepped off the bottom
            return False
        if pos[1] > self._length-1: # stepped off the top
            return False
        # anything else is good
        return True

def plot_path(path):
    """Plot the path of the walker.

    Parameters
    ----------
    path : Path
        The path of the walker to be plotted
    """
    path_x, path_y = path.get_path()
    fig, ax = plt.subplots()

    ax.plot(path_x, path_y, "-", c="blue", alpha=0.5)
    ax.plot(path_x[0], path_y[0], marker="+", c="black", markersize=6, markeredgewidth=2)
    ax.plot(path_x[-1], path_y[-1], marker="o", c="red", markersize=6)

    ax.set_xlim(0, L-1)
    ax.set_ylim(0, L-1)
    ax.set_aspect('equal')
    plt.show()

print("Starting position= ", start_pos)
walker = Walker8(start_pos)
path = Path()
path.add_step(walker)
domain = Domain(L)
for i in range(n_steps):
    walker.take_step()
    while not domain.is_valid_position(walker):
        walker.step_back()
        walker.take_step()
    path.add_step(walker)

print("Finish position= ", walker)
plot_path(path)

Output

Starting position=  (50, 50)
Finish position=  (21, 13)

Output

Task 2: Determine the average distance of each walker from its origin after a set number of steps

Now we’re going to use our simulator program to answer a question. We’d like to determine the average distance from the starting point of the walkers after each take 100 steps. To do this, we’ll start many walkers simulating and record the position they finish their walk. Then we’ll convert their finish position into a distance and determine an average. As a final twist, let’s build that average as we go. We’ll simulate 500 walkers and determine the running average after each walker completes. Let’s use Walker8 objects for this exercise

1. Adapt your program to simulate 500 walkers, one after the other. It will be useful to build a function called simulate. Record their final distances from the starting point. Report an average distance from the starting point for these 500 walkers.
2. Now extend your program to show this running average as each of the 500 walkers completes its path. Produce a plot that shows the running average

Callout-answerAnswer

random_walk_average_distance.py

def simulate(start_pos, domain_length, n_steps):
    walker = Walker8(start_pos)
    domain = Domain(domain_length)
    for i in range(n_steps):
        walker.take_step()
        while not domain.is_valid_position(walker):
            walker.step_back()
            walker.take_step()
    return walker

n_walkers = 500
walker_count = []
dist = []
avg_dist = []
fig, ax = plt.subplots()
ax.set_xlim(0, 500)
ax.set_ylim(0, 100)
for i in range(n_walkers):
    walker = simulate(start_pos, L, n_steps)
    pos = walker.get_position()
    d = ((pos[0] - start_pos[0])**2 + (pos[1] - start_pos[1])**2)**(0.5)
    dist.append(d)
    walker_count.append(i+1)
    avg = sum(dist)/walker_count[-1]
    avg_dist.append(avg)
    ax.plot(walker_count, avg_dist, "-", c="blue")
    ax.plot(walker_count[-1], dist[-1], marker="o", c="red", markersize=3)

plt.xlabel("Number of Walkers")
plt.ylabel("Distance from Start")
plt.title("Running Average Distance from Start vs Number of Walkers")
plt.show()

Output